package danran.bfs;

import java.util.*;

/**
 * @Classname PacificAtlantic
 * @Description TODO
 * @Date 2021/9/21 13:59
 * @Created by ASUS
 */
public class PacificAtlantic {

    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        boolean[][] flag1 = new boolean[heights.length][heights[0].length];
        boolean[][] flag2 = new boolean[heights.length][heights[0].length];
        boolean[][] visited = new boolean[heights.length][heights[0].length];
        // 太平洋
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < heights[0].length; i++) q.offer(new int[]{0, i});
        for (int i = 1; i < heights.length; i++) q.offer(new int[]{i, 0});
        f(heights, flag1, q, visited);
        // 大西洋
        for (int i = 0; i < heights[0].length; i++) q.offer(new int[]{heights.length - 1, i});
        for (int i = 0; i < heights.length - 1; i++) q.offer(new int[]{i, heights[0].length - 1});
        visited = new boolean[heights.length][heights[0].length];
        f(heights, flag2, q, visited);
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < flag1.length; i++) {
            for (int j = 0; j < flag1[0].length; j++) {
                if (flag1[i][j] && flag2[i][j]) ans.add(Arrays.asList(i, j));
            }
        }
        return ans;
    }

    private void f(int[][] heights, boolean[][] flag, Queue<int[]> q, boolean[][] visited) {
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int[] cur = q.poll();
                assert cur != null;
                flag[cur[0]][cur[1]] = true;
                for (int[] dir : dirs) {
                    int x = cur[0] + dir[0], y = cur[1] + dir[1];
                    if (x >= heights.length || x < 0 || y >= heights[0].length || y < 0) continue;
                    if (heights[x][y] >= heights[cur[0]][cur[1]] && !visited[x][y]) {
                        q.offer(new int[]{x, y});
                        visited[x][y] = true;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] h = new int[][]{
                {1, 2, 2, 3, 5},
                {3, 2, 3, 4, 4},
                {2, 4, 5, 3, 1},
                {6, 7, 1, 4, 5},
                {5, 1, 1, 2, 4}
        };
//        System.out.println(new PacificAtlantic().pacificAtlantic(h));
        System.out.println(new PacificAtlantic().findCircleNum(new int[][]{
                {1, 0, 0},
                {0, 1, 0},
                {0, 0, 1}}));
    }


    public int findCircleNum(int[][] matrix) {
        // 建图
        Map<Integer, List<Integer>> g = new HashMap<>();
        for (int i = 0; i < matrix.length; i++) {
            List<Integer> ch = new ArrayList<>();
            for (int j = 0; j < matrix[0].length; j++) {
                if (i != j && matrix[i][j] == 1) ch.add(j);
            }
            g.put(i, ch);
        }
//        System.out.println(g);
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < matrix.length; i++) {
            // 遍历图中的每个节点
            if (g.containsKey(i)) {// 当当前节点仍然存在图中
                q.offer(i);// 头节点入队，头节点不从图中删除，从头节点开始BFS寻找所有可以连接的节点，并将其从图中删除
                int step = 0;// 记录当前遍历的层数
                while (!q.isEmpty()) {
                    int size = q.size();
                    step++;
                    for (int j = 0; j < size; j++) {
                        Integer cur = q.poll();
                        assert cur != null;
                        // 获取连接的节点
                        List<Integer> children = g.getOrDefault(cur, new ArrayList<>());
                        for (Integer child : children) {
                            q.offer(child);// 连接的节点入队
                        }
                        // 头节点不删除
                        if (step != 1 && cur != i) g.remove(cur);
                    }
                }
            }
        }
        // 最后图中剩余的节点个数即为结果
        return g.size();
    }
}
